Networks - Summary of Kruskal's steps

Dr. J's Maths.com
Where the techniques of Maths
are explained in simple terms.

Networks and Graph Theory - Minimum spanning trees.
Summary of steps for applying Kruskal's algorithm.

Kruskal's algorithm finds a minimum spanning tree for a connected weighted graph:

starting with the shortest edge;
adding edges of increasing weight at each step;
not all edges are used in a minimum spanning tree - just a subset of the edges in the network but every vertex in the network is used.

Step 1:

In a table of 2 columns, write down the letters for the edge of smallest weight and the weight - here that is BD with a weight of 1.

BD	1

Step 2:

Write down the letters for the edge of next smallest weight and the weight. Here there are four edges each with a weight of 2 (AB, BE, CF and EF) so write them all down in any order.

BD	1
AB	2
BE	2
CF	2
EF	2

Step 3:

Continue listing edges in ascending order of their weight.

BD	1
AB	2
BE	2
CF	2
EF	2
CE	3
DE	3
AD	4
BC	4

Step 4:

Prepare a basis for the new network by copying the vertices into the approximate position they have in the original network diagram.

Step 5:

Start with the smallest edge in the table (the one you wrote down first BD) and draw a line between those vertices in your new diagram.

Step 6:

Continue to draw edges in ascending order of weight in your table until all vertices are included. Do NOT include an edge if it will create a cycle.